package functions.images;

import java.util.ArrayList;
import java.util.Date;
import java.util.Random;

import com.google.appengine.api.images.Image;

public class AlgorithmsForCloudProject {

	//private enum position { TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT };
	
	public static void main(String[] args){
		//int n = 400;
		//int shuffles = 10000000;

		int nArr[] = {5, 10, 15, 40, 100, 500, 1000, 2000, 3000, 4000, 5000};

		ArrayList<double[]> arr = new ArrayList<double[]>();
		
		for(int i = 0; i < nArr.length; ++i){
			int n = nArr[i];
			System.out.println("n = " + n);
			for(int shuffles = 10; shuffles <= 100000000; shuffles*= 10){
				double[] temp = new double[5];
				temp[0] = n;
				temp[1] = shuffles;
				long time = new Date().getTime();
				generateShuffledPuzzle_v3(n, shuffles);
				temp[2] = (new Date().getTime() - time)/1000.0;
				//System.out.println((new Date().getTime() - time)/1000.0 + " seconds for full run to finish version 3");
				//System.out.println();
				
				if(n <= 4287){
					time = new Date().getTime();
					/*prettyPrintBoard(*/generateShuffledPuzzle_v2(n, shuffles);//, n);
					/*int[] arr = generateShuffleArray_v2(n);
					for(int i = 0; i < arr.length; ++i){
						if(i > 0 && i%n == 0){
							System.out.println();
						}
						System.out.print(arr[i]);
					}
					System.out.println();*/
					temp[3] = (new Date().getTime() - time)/1000.0;
					//System.out.println((new Date().getTime() - time)/1000.0 + " seconds for full run to finish version 2");
					//System.out.println();
				} else {
					temp[3] = 100;
				}
				
				if(n <= 1000){
					time = new Date().getTime();
					generateShuffledPuzzle(n, shuffles);
					temp[4] = (new Date().getTime() - time)/1000.0;
					//System.out.println((new Date().getTime() - time)/1000.0 + " seconds for full run to finish version 1");
				} else {
					temp[4] = 100;
				}
				arr.add(temp);
			}
		}
		
		for(int j = 0; j < arr.size(); ++j){
			double[] temp = arr.get(j);
			if(temp[2] < temp[3]){
				System.out.print("*");
			}
			if(temp[4] < temp[3]){
				System.out.print("^");
			}
			System.out.println("n: " + temp[0] + "   \tshuffles: " + temp[1] + "   \tv3: " + temp[2] + "  \tv2: " + temp[3] + "  \tv3: " + temp[4]);
		}
	}
	
	public Image splitAndShuffle(Image img){
		byte[] arr = img.getImageData();
		
		for(int i = 0; i < arr.length/2; ++i){
			byte temp = arr[i];
			arr[i] = arr[(arr.length/2)+i];
			arr[(arr.length/2)+i] = temp;
		}
		
		
		return img;
	}
	
	public static void prettyPrintArrIntArr(ArrayList<int[]> arr){
		for(int i = 0; i < arr.size(); ++i){
			int[] elem = arr.get(i);
			System.out.print("(");
			for(int j = 0; j < elem.length; ++j){
				System.out.print(elem[j] + " ");
			}
			System.out.println(")");
		}
	}
	
	public static void prettyPrintBoard(int[] arr, int n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if (arr[(i * n) + j] == (n * n) - 1) {
					System.out.print("* ");
					for(int k = 1; k < Math.log10((n*n)-1); ++k){
						System.out.print(" ");
					}
				} else {
					int num = arr[(i*n) + j];
					int k;
					System.out.print(num + " ");
					if(num == 0){
						k = 1;
					} else {
						k = (int) (Math.log10(arr[(i*n)+j]) + 1);
					}
					for(; k < Math.log10((n*n)-1); ++k){
						System.out.print(" ");
					}
				}
			}
			System.out.println();
		}
	}
	
	@SuppressWarnings("rawtypes")
	public static void prettyPrintArrList(ArrayList arr){
		for(int i = 0; i < arr.size(); ++i){
			System.out.print(arr.get(i) + " ");
		}
	}
	
	public static int[] generateShuffleArray_v2(int n){
		// TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT
		//    0       1       2        3      4      5         6          7         8
		int[] arr = new int[n*n];
		int i = 0;
		long time = new Date().getTime();
		arr[i++] = 0;
		for(; i < n-1; ++i){
			arr[i] = 1;
		}
		arr[i++] = 2;
		for(int j = 1; j < n-1; ++j){
			arr[i++] = 3;
			for(int k = 1; k < n-1; ++k){
				arr[i++] = 4;
			}
			arr[i++] = 5;
		}
		arr[i++] = 6;
		for(;i<(n*n)-1;++i){
			arr[i] = 7;
		}
		arr[i++] = 8;
		
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds to finish populating the shuffle array");
		return arr;
	}
	
	public static int[] getNextArr(int starPos, int pos, int n){
		// TOP_LEFT, TOP, TOP_RIGHT, LEFT, MIDDLE, RIGHT, BOTTOM_LEFT, BOTTOM, BOTTOM_RIGHT
		//    0       1       2        3      4      5         6          7         8
		int[] toReturn = new int[1];
		switch(pos){
			case 0:
				int[] temp0 = {1,n};
				toReturn = temp0;
				break;
			case 2:
				int[] temp2 = {n-2,(2*n)-1};
				toReturn = temp2;
				break;
			case 6:
				int[] temp6 = {(n*n)-n+1,n*(n-2)};
				toReturn = temp6;
				break;
			case 8:
				int[] temp8 = {(n*n)-n-1, (n*n)-2};
				toReturn = temp8;
				break;
			case 1:
				int[] temp1 = {starPos-1, starPos+1, starPos+n};
				toReturn = temp1;
				break;
			case 3:
				int[] temp3 = {starPos-n, starPos+1, starPos+n};
				toReturn = temp3;
				break;
			case 5:
				int[] temp5 = {starPos-n, starPos-1, starPos+n};
				toReturn = temp5;
				break;
			case 7:
				int[] temp7 = {starPos-n, starPos-1, starPos+1};
				toReturn = temp7;
				break;
			case 4:
				int[] temp4 = {starPos-n, starPos-1, starPos+1, starPos+n};
				toReturn = temp4;
				break;
			default:
				System.err.println("Houston, we have a problem!");
		}
		return toReturn;
	}
	
	public static ArrayList<Integer>[] generateShuffleArray(int n){
		
		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] arr = new ArrayList[n*n];
		for(int i = 0; i < n*n; ++i){
			arr[i] = new ArrayList<Integer>();
		}
		
		long time = new Date().getTime();
		for(int i = 0; i < (n*n)-1; ++i){
			if(i/n == (i+1)/n){
				arr[i].add(i+1);
				arr[i+1].add(i);
			}
			if(i+n < (n*n)){
				arr[i].add(i+n);
				arr[i+n].add(i);
			}
		}/*
		for(int i = 0; i < n*n; ++i){
			for(int j = i+1; j < n*n; ++j){
				if((i/n == j/n && (j-i) == 1) || ((i%n == j%n) && ((j/n) - (i/n)) == 1)){
					int[] temp1 = {i,j};
					int[] temp2 = {j,i};
					arr[i].add(temp1);
					arr[j].add(temp2);
				}
			}
			//System.out.println("Finished " + i + " ring!");
		}*/
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds to finish populating the shuffle array");
		return arr;
	}
	
	public static ArrayList<int[]> trim(ArrayList<int[]> arr, int n, int[] seed){
		int max = (n*n) - 1;
		ArrayList<int[]> toReturn = new ArrayList<int[]>();
		for(int i = 0; i < arr.size(); ++i){
			int[] temp = arr.get(i);
			if(seed[temp[0]] == max || seed[temp[1]] == max){
				toReturn.add(temp);
			}
		}
		return toReturn;
	}
	
	public static int[] generateShuffledPuzzle_v3(int n, int shuffles){
		int[] seed = new int[n*n];
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		for(int i = 0; i < shuffles; ++i){
			int rand = gen.nextInt(12);
			int newPos = -1;
			if(starPos >= n*(n-1)){
				//bottom left, bottom, bottom right
				if(starPos == n*(n-1)){
					rand %= 2;
					//bottom left
					if (rand == 0){
						newPos = starPos-n;
					} else {
						newPos = starPos+1;
					}
				} else if (starPos == (n*n)-1){
					rand %= 2;
					//bottom right
					if(rand == 0){
						newPos = starPos-n;
					} else {
						newPos = starPos-1;
					}
				} else {
					rand %= 3;
					//bottom
					if(rand == 0){
						newPos = starPos-n;
					} else if (rand == 1){
						newPos = starPos-1;
					} else {
						newPos = starPos+1;
					}
				}
			} else if (starPos < n){
				//top left, top, top right
				if(starPos == 0){
					rand %= 2;
					//top left
					if(rand == 0){
						newPos = starPos+1;
					} else {
						newPos = starPos+n;
					}
				} else if (starPos == (n-1)){
					rand %= 2;
					//top right
					if(rand == 0){
						newPos = starPos-1;
					} else {
						newPos = starPos+n;
					}
				} else {
					rand %= 3;
					//top
					if(rand == 0){
						newPos = starPos-1;
					} else if (rand == 1) {
						newPos = starPos+1;
					} else {
						newPos = starPos+n;
					}
				}
			} else if (starPos % n == 0){
				rand %= 3;
				//left
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos+1;
				} else {
					newPos = starPos+n;
				}
			} else if (starPos % n == (n-1)){
				rand %= 3;
				//right
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos-1;
				} else {
					newPos = starPos+n;
				}
			} else {
				rand %= 4;
				// middle
				if(rand == 0){
					newPos = starPos-n;
				} else if (rand == 1) {
					newPos = starPos-1;
				} else if (rand == 2) {
					newPos = starPos+1;
				} else {
					newPos = starPos+n;
				}
			}
			if (newPos < 0) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			seed[starPos] = seed[newPos];
			seed[newPos] = (n*n)-1;
			starPos = newPos;
			//prettyPrintBoard(seed, n);
			//System.out.println();
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
	
	public static int[] generateShuffledPuzzle_v2(int n, int shuffles){
		int[] seed = new int[n*n];
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		int[] shuffleArr = generateShuffleArray_v2(n);
		/*for(int i = 0; i < shuffleArr.length; ++i){
			System.out.print(i+": ");
			prettyPrintArrList(shuffleArr[i]);
			System.out.println();
		}*/
		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		for(int i = 0; i < shuffles; ++i){
			int[] tempArr = getNextArr(starPos, shuffleArr[starPos], n);
			int temp = tempArr[gen.nextInt(tempArr.length)];
			if (seed[starPos] != (n * n) - 1) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			seed[starPos] = seed[temp];
			seed[temp] = (n*n)-1;
			starPos = temp;
			//prettyPrintBoard(seed, n);
			//System.out.println();
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
	
	public static int[] generateShuffledPuzzle(int n, int shuffles){
		int[] seed = new int[n*n];
		for(int i = 0; i < n*n; ++i){
			seed[i] = i;
		}
		
		ArrayList<Integer>[] shuffleArr = generateShuffleArray(n);
		/*for(int i = 0; i < shuffleArr.length; ++i){
			System.out.print(i+": ");
			prettyPrintArrList(shuffleArr[i]);
			System.out.println();
		}*/
		Random gen = new Random();
		long time = new Date().getTime();
		int starPos = (n*n)-1;
		for(int i = 0; i < shuffles; ++i){
			ArrayList<Integer> tempAL = shuffleArr[starPos];
			int temp = tempAL.get(gen.nextInt(tempAL.size()));
			if (seed[starPos] != (n * n) - 1) {
				--i;
				System.out.println("PROBLEM");
				continue;
			}
			seed[starPos] = seed[temp];
			seed[temp] = (n*n)-1;
			starPos = temp;
			//prettyPrintBoard(seed, n);
			//System.out.println();
		}
		System.out.println((new Date().getTime() - time)/1000.0 + " seconds for the shuffling");
		return seed;
	}
}
